aliases:
- Regular languageA language L is said regular if there exists a finite automaton that accepts L.
The language of all binary strings that contain the string
We must find an automaton that accepts it.
So we must seek the patter of two zeros followed by a 1.
A collection of objects is closed under some operation if applying that operation to members of the collection returns an object in the collection.
In the set of natural numbers, addition is such an operation, while division is not.
Regular languages are closed(the result is a regular language) under these 3 operations:
But we need to prove this.
A string is accepted by an automata if and only if the automata starting at the initial state ends in an accepting state after reading the string.
A language accepted by an automata is a set of strings accepted by the automata.
How do i prove that the if A and B are regular, the union(for example) of A and B is still regular?
We create a general automaton and show that it recognizes the resulting language.
A language is regular if every string is accepted by at least one automata.
Let
Their union will be
The solution is to make an automaton that sends the strings to both the automatas that accepted
These are not all the possible permutations, only the ones that start with a string from the first set.
Let
Their concatenation will be
The solution is to make an automaton that accepts the strings that belong to the set
Star is the concatenation of a language with itself as many times as you want.
The solution is to take the original automata and make arrows that go from the final states to the initial states. If the string is finished it stays in the accepted state, if not it begins again from the start.
This can accept every permutation.